import java.util.*;

 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }


public class TextDemo {
    public boolean isSubtreeDepth(TreeNode root, TreeNode subRoot) {
        return dft(root,subRoot);
    }
    private boolean dft(TreeNode root,TreeNode subRoot){
        if(root==null){
            return subRoot==null;
        }
        return check(root,subRoot)||dft(root.left,subRoot)||dft(root.right,subRoot);
    }
    private boolean check(TreeNode root,TreeNode subRoot){
        if(root==null&&subRoot==null){
            return true;
        }
        if (root == null || subRoot == null || root.val != subRoot.val) {
            return false;
        }
        return check(root.left,subRoot.left)&&check(root.right,subRoot.right);
    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isSum(root.left,root.right);
    }
    private boolean isSum(TreeNode rootleft,TreeNode rootright){
        if(rootleft==null&&rootright==null){
            return true;
        }
        if(rootleft==null||rootright==null||rootleft.val!=rootright.val){
            return false;
        }

        boolean left = isSum(rootleft.left,rootright.right);
        boolean right = isSum(rootleft.right,rootright.left);

        return left&&right;

    }
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        return Math.max(leftDepth,rightDepth)+1;

    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> List = new ArrayList<>();
        if(root==null){
            return List;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){

            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for(int i = 0;i<size;i++){
                TreeNode head = queue.poll();
                list.add(head.val);
                if(head.left!=null){
                    queue.offer(head.left);
                }
                if(head.right!=null){
                    queue.offer(head.right);
                }
            }
            List.add(list);
        }
        return List;

    }
    int preorderIndex = 0;
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return build(preorder,0,inorder.length-1);

    }
    public TreeNode build(int[] preorder,int left,int right){
        if(left>right){
            return null;
        }
        int val = preorder[preorderIndex];
        int Index = map.get(val);
        preorderIndex++;

        TreeNode head = new TreeNode(val);
        head.left = build(preorder,left,Index-1);
        head.right = build(preorder,Index+1,right);
        return head;
    }
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {

        int m = grid.length;
        int n = grid[0].length;
        for(int t = 0;t<k;t++){

            int[][] newgrid = new int[m][n];
            for(int i = 0;i<m;i++){
                for(int j = 0;j<n-1;j++){
                    newgrid[i][j+1] = grid[i][j];
                }
            }

            for(int i =0;i<m-1;i++){
                newgrid[i+1][0] = grid[i][n-1];
            }

            newgrid[0][0] = grid[m-1][n-1];
            grid = newgrid;
        }
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0;i<m;i++){
            List<Integer> list = new ArrayList<>();
            for(int j = 0;j<n;j++){
                list.add(grid[i][j]);
            }
            result.add(list);
        }
        return result;
    }
    public boolean IsPopOrder(int [] push,int [] pop) {
        if(push.length!=pop.length){
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0;i<push.length;i++){
            stack.push(push[i]);
            while(!stack.isEmpty()&&stack.peek()==pop[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();

    }

    public static void main(String[] args) {
        StringBuilder str = new StringBuilder();
        str.deleteCharAt(str.length()-1);
    }
    public boolean backspaceCompare(String S, String T) {
        int skipS = 0;
        int skipT = 0;
        int i = S.length()-1;
        int j = T.length()-1;
        while(i>=0||j>=0){
            while(i>=0){
                if(S.charAt(i)=='#'){
                    skipS++;
                    i--;
                }else if(skipS>0){
                    skipS--;
                    i--;
                }else{
                    break;
                }
            }
            while(j>=0){
                if(T.charAt(j)=='#'){
                    skipT++;
                    j--;
                }else if(skipT>0){
                    skipT--;
                    j--;
                }else{
                    break;
                }
            }
            if(i>=0&&j>=0){
                if(S.charAt(i)!=T.charAt(j)){
                    return false;
                }
            }else{
                if(i>=0||j>=0){
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }

}
